package com.ryujung.greedy;

class Solution53 {
    /**
     * 分治算法
     * 思路：
     * 将一个序列分为多个子序列，然后每个子序列中获取其最大值，然后合并结果
     * 方式：递归
     * <p>
     * TODO 分治算法略微复杂，而且本题看似不是必要的，暂时先放下，等后面遇到相同算法的题目再完成
     */
    public int maxSubArray(int[] nums) {
        return helper(nums, 0, nums.length - 1);
    }

    private int helper(int[] nums, int left, int right) {

        return 0;
    }

    /**
     * 思路：
     * 首先定义一个最大值max，和当前正在计算的子序和 sum
     * 遍历数组，
     * 对每个元素的操作分为两种情况：继续累加、或直接赋给sum
     * 判断条件：当前的sum值是否>0？累加：重新赋值
     * 然后用sum判断并更新max的最大值
     * <p>
     * 注意：
     * 需要考虑序列全部为负数的情况，是否需要特殊处理
     */
    public int maxSubArray1(int[] nums) {
        int sum = 0, max = nums[0];
        for (int num : nums) {
            // 如果当前收益小于0，重新取值，否则相加
            sum = sum > 0 ? sum + num : num;
            // 更新最大值
            max = Math.max(sum, max);
        }
        return max;
    }

    public static void main(String[] args) {
        Solution53 s = new Solution53();
        System.out.println(s.maxSubArray(new int[]{1, 2}));
        System.out.println(s.maxSubArray(new int[]{1}));
        System.out.println(s.maxSubArray(new int[]{-1, -2, -3}));
    }
}